DEFINITION MODULE  LongSets;

(*****************************************************************************)
(* Die vorliegende MODULA-Implementation stellt nur Mengen mit maximal 16    *)
(* Elementen zur Verfuegung. Da sich mancherlei Dinge sehr elegant mit Mengen*)
(* und den auf ihnen definierten Operationen loesen lassen, stellt dieses Mo-*)
(* dul Mengenoperationen zur Verfuegung, die mit einem hier zu definierenden *)
(* Mengentyp arbeiten.                                                       *)
(*                                                                           *)
(* Die Menge selber ist ein ARRAY von BITSETs; je nach Anwendung muss nun    *)
(* noch der Typ der Mengenelemente angegeben werden ( SetElement = ... ).    *)
(* Das kann durch Aufzaehlung geschehen - SetElement = ( e1, e2, e3 ... en ) *)
(* oder durch Angabe eines Standardtyps, hier ist aber nur CHAR sinnvoll.    *)
(* Wenn ein Unterbereichstyp angegeben werden soll, muss die untere Grenze   *)
(* mit Null beginnen - SetElement = [0..1023].                               *)
(*                                                                           *)
(* Ist der Typ festgelegt, muessen Definitios- und Implementationsmodul neu  *)
(* uebersetzt werden; eine Aenderung der Prozeduren ist nicht notwendig      *)
(*                                                                           *)
(* Bei den Hinweisen auf die aequivalenten logischen Operationen ist zu be-  *)
(* achten, dass bitweise Operationen gemeint sind.                           *)
(*___________________________________________________________________________*)
(*   10-Jan-89 , Holger Kleinschmidt                                         *)
(*****************************************************************************)

FROM  SYSTEM  IMPORT  (* PROC *) VAL;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)

  TYPE
        SetElement   = CHAR;

  (* Als 'SetElement' kann ein beliebiger Aufzaehlungstyp,
   * oder ein nichtstrukturierter Typ  wie CHAR oder
   * CARDINAL stehen. Bei Standardtypen wie CARDINAL
   * ist allerdings Vorsicht geboten: die haben meistens
   * eine sehr grosse Anzahl Elemente...
   *)


  CONST
        ElementsInBITSET = 16;
        ElementsInSet    = VAL( CARDINAL, MAX(SetElement) ) + 1;

        NoOfBITSETs      = (( ElementsInSet - 1 ) DIV ElementsInBITSET ) + 1;
        LastElements     = (( ElementsInSet - 1 ) MOD ElementsInBITSET ) + 1;

        (* "LastElements" enthaelt die Anzahl der belegten Bits
         * in der Letzten BITSET; Ist "ElementsInSet" ein Vielfaches
         * von 16, so ist "LastElements" = 16, wird nur ein Element
         * in der letzten BITSET benutzt, so ist "LastElements" = 1
         *)


  TYPE
        Set              = ARRAY [ 0..NoOfBITSETs - 1 ] OF  BITSET;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)


  PROCEDURE NoElements  ((* -- /AUS *) VAR  menge : Set );

  PROCEDURE AllElements ((* -- /AUS *) VAR  menge : Set );

 (*-------------------------------------------------------------------------
  | Loescht, bzw. setzt alle Elemente von <menge>.                          |
   -------------------------------------------------------------------------*)


  PROCEDURE IsEmptySet ((* EIN/ -- *) menge : Set ): BOOLEAN;

  PROCEDURE IsFullSet  ((* EIN/ -- *) menge : Set ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Prueft, ob <menge> leer ist,bzw. alle moeglichen Elemente enthalten sind|
   -------------------------------------------------------------------------*)


  PROCEDURE Complement ((* EIN/ -- *)     menge : Set;
                        (* -- /AUS *) VAR compl : Set  );

 (*-------------------------------------------------------------------------
  | <compl> enthaelt die Komplemaentaermenge von <menge>, d.h. in <compl>   |
  | sind genau die Elemente enthalten, die in <menge> nicht enthalten sind. |
  |                                                                         |
  | Dies ist die logische Operation:   <compl> := NOT <menge>               |
   -------------------------------------------------------------------------*)


  PROCEDURE Card ((* EIN/ -- *) menge : Set ): CARDINAL;

 (*-------------------------------------------------------------------------
  | Liefert die Kardinalitaet, d.h. die Anzahl der Elemente von <menge>.    |
   -------------------------------------------------------------------------*)


  PROCEDURE IsElement ((* EIN/ -- *) elem  : SetElement;
                       (* EIN/ -- *) menge : Set        ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Testet, ob das Element <elem> in der Menge <menge> enthalten ist.       |
   -------------------------------------------------------------------------*)


  PROCEDURE Include ((* EIN/ -- *)     elem  : SetElement;
                     (* EIN/AUS *) VAR menge : Set        );

  PROCEDURE Exclude ((* EIN/ -- *)     elem  : SetElement;
                     (* EIN/AUS *) VAR menge : Set        );

 (*-------------------------------------------------------------------------
  | Fuegt das Element <elem> der Menge <menge> hinzu, bzw. entfernt es.     |
  |  - Falls <elem> bei Aufruf von "Include" bereits in der Menge enthalten |
  |    ist, wird <menge> nicht veraendert                                   |
  |  - Falls <elem> bei Aufruf von "Exclude" nicht in der Menge enthalten   |
  |    ist, wird <menge> nicht veraendert                                   |
   -------------------------------------------------------------------------*)

  PROCEDURE IncludeRange ((* EIN/ -- *)     von,
                          (* EIN/ -- *)     bis   : SetElement;
                          (* EIN/AUS *) VAR menge : Set        );

  PROCEDURE ExcludeRange ((* EIN/ -- *)     von,
                          (* EIN/ -- *)     bis   : SetElement;
                          (* EIN/AUS *) VAR menge : Set        );

 (*-------------------------------------------------------------------------
  | Der Bereich von Elementen zwischen <von> und <bis> ( einschliesslich )  |
  | wird <menge> hinzugefuegt, bzw. aus <menge> entfernt.                   |
  |  - Liegt <bis> vor <vor>, passiert nichts.                              |
  |  - Liegt <bis> ausserhalb von <menge>, werden nur die Elemente bis zum  |
  |    Mengenende beruecksichtigt.                                          |
   -------------------------------------------------------------------------*)


  PROCEDURE Union ((* EIN/ -- *)     menge1,
                   (* EIN/ -- *)     menge2 : Set;
                   (* -- /AUS *) VAR verein : Set  );

 (*-------------------------------------------------------------------------
  | Bildet die Vereinigungsmenge. D.h. <verein> enthaelt alle Elemente von  |
  | <menge1> und <menge2>. In beiden Mengen auftretende Elemente sind in    |
  | <verein> nur einmal enthalten.                                          |
  |                                                                         |
  | Dies ist die logische Operation:   <verein> := <menge1> OR <menge2>     |
   -------------------------------------------------------------------------*)


  PROCEDURE Intersection ((* EIN/ -- *)     menge1,
                          (* EIN/ -- *)     menge2  : Set;
                          (* -- /AUS *) VAR schnitt : Set  );

 (*-------------------------------------------------------------------------
  | Bildet die Schnittmenge. D.h. <schnitt> enthaelt die Elemente, die so-  |
  | wohl in <menge1> als auch in <menge2> enthalten sind.                   |
  |                                                                         |
  | Dies ist die logische Operation:   <schnitt> := <menge1> AND <menge2>   |
   -------------------------------------------------------------------------*)


  PROCEDURE Difference ((* EIN/ -- *)     menge1,
                        (* EIN/ -- *)     menge2 : Set;
                        (* -- /AUS *) VAR diff   : Set  );

 (*-------------------------------------------------------------------------
  | Bildet die Differenzmenge. D.h. in <diff> sind alle Elemente von        |
  | <menge1> enthalten, die nicht auch in <menge2> enthalten sind.          |
  |                                                                         |
  | Dies ist die logische Operation:   <diff> := <menge1> AND NOT <menge2>  |
   -------------------------------------------------------------------------*)


  PROCEDURE SymmetricDiff ((* EIN/ -- *)     menge1,
                           (* EIN/ -- *)     menge2  : Set;
                           (* -- /AUS *) VAR symdiff : Set  );

 (*-------------------------------------------------------------------------
  | Bildet die symmetrische Differenz. D.h. in <symdiff> sind alle Elemente |
  | enthalten, die entweder in <menge1> oder in <menge2> enthalten sind,    |
  | nicht aber in beiden. Die symmetrische Differenz ist die Differenzmenge |
  | von Vereinigungs - und Schnittmenge.                                    |
  |                                                                         |
  | Dies ist die logische Operation:   <symdiff> := <menge1> XOR <menge2>   |
   -------------------------------------------------------------------------*)


  PROCEDURE Equal ((* EIN/ -- *) menge1,
                   (* EIN/ -- *) menge2 : Set ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Testet, ob <menge1> und <menge2> gleich sind.                           |
   -------------------------------------------------------------------------*)


  PROCEDURE IsSubset       ((* EIN/ -- *) menge1,
                            (* EIN/ -- *) menge2 : Set ): BOOLEAN;

  PROCEDURE IsProperSubset ((* EIN/ -- *) menge1,
                            (* EIN/ -- *) menge2 : Set ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Testet, ob <menge1> eine ( echte ) Teilmenge von <menge2> ist, d.h. ob  |
  | alle Elemente von <menge1> auch in <menge2> enthalten sind.             |
  | "IsProperSubset" verlangt zusaetzlich noch, dass die beiden Mengen nicht|
  | gleich sind.                                                            |
  |                                                                         |
  | Dies ist die logische Operation:     <menge1> AND NOT <menge2> = 0      |
   -------------------------------------------------------------------------*)


  PROCEDURE IsSuperset       ((* EIN/ -- *) menge1,
                              (* EIN/ -- *) menge2 : Set ): BOOLEAN;

  PROCEDURE IsProperSuperset ((* EIN/ -- *) menge1,
                              (* EIN/ -- *) menge2 : Set ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Testet, ob <menge1> eine ( echte ) Obermenge von <menge2> ist, d.h. ob  |
  | alle Elemente von <menge2> auch in <menge1> enthalten sind.             |
  | "IsProperSuperset" verlangt zusaetzlich noch, dass die beiden Mengen    |
  | nicht gleich sind.                                                      |
  |                                                                         |
  | Dies ist die logische Operation:     <menge2> AND NOT <menge1> = 0      |
   -------------------------------------------------------------------------*)


  PROCEDURE WriteSet ((* EIN/ -- *) menge : Set );

 (*-------------------------------------------------------------------------
  | Ist der Versuch, eine Menge auszugeben.                                 |
  | Pro Zeile werden vier BITSETs ausgegeben, jeweils getrennt durch '|'.   |
  | Fuer ein vorhandenes Element wird ein '1', fuer ein nicht vorhandenes   |
  | Element '0' geschrieben. Es werden genau soviele Elemente dargestellt,  |
  | wie maximal in "Set" vorhanden sein koennen. Evtl. zusaetzliche Bits in |
  | der letzten BITSET werden nicht dargestellt.                            |
  | Die Position der Elemente nimmt von links nach rechts und von oben nach |
  | unten zu.                                                               |
  | Die Prozedur ist eigentlich nur zu Testzwecken gedacht.                 |
   -------------------------------------------------------------------------*)

END  LongSets.
